﻿// 0902train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
字母代表一个节点值，左右括号内包含该节点的子节点
左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空

输入
a{b{e},c{,d}}
输出
ebacd

中序遍历各节点值
 */
class Solution01
{
public:
    struct TreeNode
    {
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        char val;
        TreeNode() = default;
        TreeNode(char val) :val(val) {};
    };
    void inorder(TreeNode* root)
    {
        if (root == nullptr) return;
        inorder(root->left);
        cout << root->val;
        inorder(root->right);
    }
    Solution01(string&origin_str)
    {
        vector<TreeNode*>stack_v;
        //根节点
        TreeNode* root = new TreeNode(origin_str[0]);
        stack_v.push_back(root);
        /*
         1如果遇到左括号，is_left=true
         下一个节点，栈顶节点的左节点
         2遇到逗号，如果is_left=true，表示栈顶节点无左节点
         is_left=false,is_right=true
         3遇到字母，如果is_left=true,当前节点为栈顶左节点，is_right=false
         4遇到右括号，栈顶节点出栈
         */
        bool is_left = false, is_right = false;
        for (int i=1; i<origin_str.size(); i++)
        {
            char curr_char = origin_str[i];

            if (curr_char=='{')
            {
                is_left = true;
            }
            else if (curr_char==',')
            {
                //说明没有左节点
                if (is_left) is_left = false;
                //下一个节点是右节点
                is_right = true;
            }
            else if (curr_char=='}')
            {
	            if (i!=origin_str.size()-1 && origin_str[i + 1] == '}')
				{
                    stack_v.pop_back();
				}
            }
            else
            {
                TreeNode* curr_node = new TreeNode(curr_char);
                //遇到字母
                if (is_left)
                {
                    stack_v.back()->left = curr_node;
                    is_left = false;
                }
                else if (is_right)
                {
                    stack_v.back()->right = curr_node;
                    is_right = false;
                }
                //如果字母下一个是左括号，那么表示下个节点是左节点，b{e}
                //需要入栈
                //如果字母下一个是右括号，那么栈顶出栈
                if (origin_str[i+1]=='{')
                {
                    stack_v.push_back(curr_node);
                }
                else if (origin_str[i+1]=='}')
                {
                    stack_v.pop_back();
                }
            }


            //for
        }

        inorder(root);

	    //Solution01
    }
};


/*
 给一个正整数 NUM1，计算出新正整数 NUM2
 NUM2 为 NUM1 中移除 N 位数字后的结果，需要使得 NUM2 的值最小
输入
1. 输入的第一行为一个字符串，字符串由 0-9 字符组成，记录正整数 NUM1，NUM1 长度小于 32
2. 输入的第二行为需要移除的数字的个数，小于 NUM1 长度。
输出
输出一个数字字符串，记录最小值 NUM2

输入
2615371
4
输出
131
移除 2、6、5、7 这四个数字，剩下 1、3、1 按原有顺序排列组成 131 为最小值

如果左边比当前大，就移除
 */
class Solution02
{
public:
    Solution02(string&num_str, int limit)
    {
        vector<int>stack_v;
	    for (int i=0; i<num_str.size(); i++)
	    {
            int curr_num = num_str[i] - '0';
		    while (!stack_v.empty()&&stack_v.back()>curr_num &&limit>0)
		    {
                stack_v.pop_back();
                limit--;
		    }
            stack_v.push_back(curr_num);
	    }

        /*
         10345
         2
         */
        if (limit>0)
        {
            //0 value 1 index
            vector<vector<int>>sort_vec;
            for (int i=0; i<stack_v.size();i++)
            {
                vector<int>min_sort = { stack_v[i], i };
                sort_vec.push_back(min_sort);
            }
            sort(sort_vec.begin(), sort_vec.end(), [](vector<int>&a, vector<int>&b)
                {
                    if (a[0] == b[0])
                        return a[1] < b[1];
                    return a[0] > b[0];
                });

            sort_vec = vector<vector<int>>(sort_vec.begin(), sort_vec.begin() + limit);

            unordered_set<int>erase_index;
            for (auto&num_vec:sort_vec)
            {
                erase_index.insert(num_vec[1]);
            }

            vector<int>new_vec;
            for (int i=0; i<sort_vec.size(); i++)
            {
                if (erase_index.count(i) > 0)
                    continue;
                new_vec.push_back(stack_v[i]);
            }
            stack_v = new_vec;
        }

        string result;
        for (auto&num:stack_v)
        {
            result += to_string(num);
        }
        cout << result;
    }
};


/*
 一个长整型数字，消除重复的数字后，得到最大的一个数字
如 12341 ，消除重复的 1，可得到 1234 或 2341，取最大值 2341
如 42234，消除 4 得到 4223 或者 2234 ，再消除 2，得到 423 或 234，取最大值 423

输入
输入一个数字，范围 [1, 100000]
输出
输出经过删除操作后的最大值

输入
12341
输出
2341

删掉左边比当前小的数
 */
class Solution03
{
public:
    Solution03(string&num_str)
    {
        unordered_map<int, vector<int>>repeat_map;

        vector<int>repeat_vec(10);

        for (auto&num_char:num_str)
        {
            int num = num_char - '0';
            repeat_vec[num] += 1;
        }

        //扫一遍num_str记录坐标
        for (int i=0; i<num_str.size(); i++)
        {
            int num = num_str[i] - '0';
	        if (repeat_vec[num]>=2)
	        {
                repeat_map[num].push_back(i);
	        }
        }

        vector<int>stack_v; //存坐标
        //正序，删除左边<=当前
        for (int i=0; i<num_str.size(); i++)
        {
            int curr = num_str[i] - '0';
            
            //pop的时候，直接改repeat_map的数组就行了
            //如果此时.size()已经==1,那就不改，依然pop
            while (!stack_v.empty()&&num_str[stack_v.back()]-'0'<curr)
            {
                int top_i = stack_v.back();
                int top_num = num_str[stack_v.back()] - '0';
                stack_v.pop_back();

                //找到repeat_map数组里的坐标给删掉就完事了
                if (repeat_map.count(top_num)>0 && repeat_map.at(top_num).size()>1)
                {
                    //左边小于当前，删掉左边
                    vector<int>new_vec;
                    for (auto& index : repeat_map[top_num])
                    {
                        if (index == top_i)continue;
                        new_vec.push_back(index);
                    }
                    repeat_map[top_num] = new_vec;
                }
                //while
            }
            //如果栈为空，或者栈顶>当前，可以入栈
        	if (stack_v.empty())
        	{
                stack_v.push_back(i);
        	}
        	else if (!stack_v.empty()&& num_str[stack_v.back()] - '0' > curr)
            {
                stack_v.push_back(i);
            }
        	else if (!stack_v.empty() &&num_str[stack_v.back()] - '0' == curr)
            {
                //如果栈顶跟现在相等，移除i
                //左边等于当前，删掉当前的数
                vector<int>new_vec;
                for (auto& index : repeat_map[curr])
                {
                    if (index == i)continue;
                    new_vec.push_back(index);
                }
                
                repeat_map[curr] = new_vec;
            }
            
        }

        string result;
        for (int i=0; i<num_str.size();i++)
        {
            int curr = num_str[i] - '0';
            if (repeat_map.count(curr)>0 && i!=repeat_map.at(curr)[0])
            {
	            //数组里没有就是要删除的元素
                continue;
            }
            result += num_str[i];
        }
        cout << result;
        //Solution03
    }
};

class Solution13
{
public:
    Solution13(string&num_str)
    {
		//1如果已经使用过，直接跳过
        //2正序遍历，左边比当前小，且左边计数大于1，pop
        vector<int>num_count_vec(10);
        for (auto&num_char:num_str)
        {
            int num = num_char - '0';
            num_count_vec[num] += 1;
        }

        //因为只保留一个，记录过的数，不再入栈
        unordered_set<int>used_num;

        vector<int>stack_v;
        for (int i=0; i<num_str.size(); i++)
        {
            int curr = num_str[i] - '0';
            if (used_num.count(curr)>0)
            {
                //记录过的数，不再入栈
                num_count_vec[curr] -= 1;
            }
            else
            {
                //栈不为空，栈顶小于当前，栈顶计数大于1
	            while (!stack_v.empty()&&stack_v.back()<curr&&num_count_vec[stack_v.back()]>0)
	            {
                    int top_num = stack_v.back();
                    stack_v.pop_back();
                    used_num.erase(top_num);
	            }
                stack_v.push_back(curr);
                used_num.insert(curr);
                num_count_vec[curr] -= 1;
            }
        }

        string result;
        for (auto&num:stack_v)
        {
            result += to_string(num);
        }
        cout << result;
        //Solution13
    }
};

int main()
{
	{
        string num_str = "605481041183871";
        //string num_str;
        //cin >> num_str;
        Solution13 solu(num_str);

        return 0;
	}
	{
        //string input = "2615371";
        //int limit = 4;
        string input;
        cin >> input;
        int limit;
        cin >> limit;
        Solution02 solu(input, limit);

        return 0;
	}
    //a{b{d,e{g,h{,i}}},c{f}} dbgehiafc
    //a{b{d{C,D{E{,F}}},e{g,h{A{,B},i}}},c{f}}
    //string input = "a{b{d{C,D{E{,F}}},e{g,h{A{,B},i}}},c{f}}";
    string input;
    getline(cin, input);
    Solution01 solu(input);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
